package 力扣.动态规划;

import java.util.Arrays;

public class 比特位计数338 {
    public static void main(String[] args) {
        int[] ints = countBits2(10);
        System.out.println(Arrays.toString(ints));
    }
    //理解版：后面的数字的二进制都是前面的数字的二进制拼接的
    public static int[] countBits(int num) {
        int[] ints = new int[num + 1];
        int te = 0;
        for (int i = 1 ; i <=num ; i++) {
            if (( i & (i-1) )== 0){//只要是2的幂 只有1个
                te = i;
                ints[i] = 1;
                continue;
            }
            if( i % 2 == 0){
                ints[i] = ints[i -te] + 1;// 在2的幂之后的数 都是之前求过的数，直用即可，然后再加上2的幂（也就是1）
            }else{
                ints[i] = ints[i -1] + 1;//奇数是前一位偶数+1
            }
        }
        return ints;
    }
    //进阶版 最低有效位
    //**最低有效位**。 利用 `n & (n-1)` 可以去除 n（实际是比特位）中最后的一位1,得到一个新的数, 此时,这个数肯定小于n ,它已被我们求出。
    // 根据动态规划的原理，直接用即可。
    public static int[] countBits2(int num) {
        int []ints = new int[num + 1];
        for (int i = 1; i <=num ; i++) {
             ints[i] = ints[ i & ( i - 1 )] +1;//递推关系式
        }
        return ints;
    }
}
